package com.lgc.algorithm.quick;

public class QuickSort {
    public static void main(String args[]) {

        // 快速排序法的平均复杂度为 O(nlogn)
        /*通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，
        然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。*/

        //实际上我们排序的目的就是为了让左侧的值比右侧的值小，那么我们就可以取一个基准值,一般用第一个数作基准值。

        int[] numbers = new int[]{
                //3, 2, 1, 4
                //10,20,15,0,6,7,2,1,-5,55
                6, 3, 1, 7, 2, 3, 2, 5, 8
        };
        quickSort(numbers, 0, numbers.length - 1);

        int[] numbers2 = new int[]{
                1, 2, 3, 4
        };
        quickSort(numbers2, 0, numbers2.length - 1);

        for (int i = 0; i < numbers.length; i++) {
            System.out.println(numbers[i]);
        }
    }

    /**
     * @param numbers 带排序数组
     * @param low     开始位置
     * @param high    结束位置
     */
    public static void quickSort(int[] numbers, int low, int high) {
        if (low < high) {
            //将numbers数组进行一分为二
            int mid = getMiddle(numbers, low, high);

            //对低字段表进行递归排序
            quickSort(numbers, low, mid - 1);

            //对高字段表进行递归排序
            quickSort(numbers, mid + 1, high);
        }
    }

    /**
     * 查找出中轴（默认是最低位low）的在numbers数组排序后所在位置
     *
     * @param numbers 带查找数组
     * @param low     开始位置
     * @param high    结束位置
     * @return 中轴所在位置
     */
    public static int getMiddle(int[] numbers, int low, int high) {
        //数组的第一个作为基数(中轴)
        int base = numbers[low];
        //记录基数的下标
        int index = low;

        while (low < high) {
            while (low < high && numbers[high] >= base) {
                high--;
            }
            numbers[index] = numbers[high];//将基数所在下标对应的值改为找到的比基数小的值
            index = high;//修改基数所在的下标位置
            numbers[high] = base;//将找到的比基数小的位置的值改为基数的值

            while (low < high && numbers[low] <= base) {
                low++;
            }
            numbers[index] = numbers[low];
            index = low;
            numbers[low] = base;
        }

        // 返回中轴的位置
        return index;
    }
}
